#include "../../head/myhead.h"

template <class T>

/**
 * *********************************************************************************************************************
 * *******************************************************数组********************************************************
 * *********************************************************************************************************************
 */

int getLength(T &array)
{
    return sizeof(array) / sizeof(array[0]);
}

void printArray(int array[], int length)
{
    for (int i = 0; i < length; i++)
    {
        cout << array[i] << " ,";
    }
    cout << endl;
}
/**
 * 给定一个升序数组arr，数组元素有负数，请你按绝对值大小将其重新按升序排序，
 * 不更改元素本身的值，只改变数组中元素的顺序
 * 思路：双指针，定义两个指针i，j。定义一个空数组，长度与原数组一样首先i,j同时向后移动，直到arr[j] > 0退出
 * 然后两个元素i从当前位置向前遍历，j从当前位置向后遍历。
 * 错误原因：i和j在分界点未找清楚
 */
void rankArrayByAbsoluteValue(int nums[], int length)
{
    int i = 0, j = 0, k = 0;
    int *temp = (int *)malloc(length * sizeof(int));
    while (nums[j] < 0)
        j++;
    i = j - 1;
    while (i >= 0 || j < length)
    {
        if ((0 - nums[i]) < nums[j])
        {
            temp[k++] = nums[i];
            i--;
        }
        else
        {
            temp[k++] = nums[j];
            j++;
        }
    }
    while (i >= 0)
    {
        temp[k++] = nums[i];
        i--;
    }
    while (j < length)
    {
        temp[k++] = nums[j];
        j++;
    }

    for (i = 0; i < length; i++)
    {
        nums[i] = temp[i];
        int a = temp[i];
        cout << a << endl;
    }
}

/**
 * 输入一行由大写字母组成的字符串，数一数有多少个QAQ？QAQ三个字母任意一个位置不同，则总数+1，
 * 例如 QAQQ 位置123，算一个QAQ，而位置124也算一个QAQ，因此共有两个QAQ，答案为2
 * 输入： QAQAQBCDEF 输出： 4解释：123，125，145，345 (数字代表字母的位置)，以上共有4个QAQ
 */
int countQAQ(char arr[], int len)
{
    int cnt = 0;
    int pre[MAXSIZE] = {0}; // pre[i]表示从第0个到第i-1个字母有多少Q
    for (int i = 1; i <= len; i++)
    {
        if (arr[i - 1] == 'Q')
            pre[i] = pre[i - 1] + 1;
        else
            pre[i] = pre[i - 1];
    }
    for (int i = 0; i < len; i++)
    {
        if (arr[i] == 'A')
            cnt += pre[i] * (pre[len] - pre[i]);
    }
    return cnt;
}

/**
 * 判断子序列：输入两个串，判断B是否为A的子序列
 * 本题询问的是，s 是否是 t 的子序列，因此只要能找到任意一种 s 在 t 中出现的方式，即可认为 s 是 t 的子序列。
 * 而当我们从前往后匹配，可以发现每次贪心地匹配靠前的字符是最优决策。
 * 假定当前需要匹配字符 c，而字符 c 在 t 中的位置 x1 和 x2出现（x1 < x 2），
 * 那么贪心取 x1 是最优解，因为 x2 后面能取到的字符，x1 也都能取到，并且通过 x1 与 x2 之间的可选字符，更有希望能匹配成功。
 * 这样，我们初始化两个指针 i 和 j，分别指向 s 和 t 的初始位置。
 * 每次贪心地匹配，匹配成功则 i 和 j 同时右移，匹配 s 的下一个位置，匹配失败则 j 右移，i 不变，尝试用 t 的下一个字符匹配 s。
 * 最终如果 i 移动到 s 的末尾，就说明 s 是 t 的子序列
 */
bool isSubsequence(char *s, char *t)
{
    int n = strlen(s), m = strlen(t);
    int i = 0, j = 0;
    while (i < n && j < m)
    {
        if (s[i] == t[j])
        {
            i++;
        }
        j++;
    }
    return i == n;
}

/**
 * 王道2.2.3.08.线性表(a),az,a3,…,an)中的元素递增有序且按顺序存储于计算机内。
 * 要求设计一个算法，完成用最少时间在表中查找数值为x的元素，若找到，则将其与后继元素位置相交换，
 * 若找不到，则将其插入表中并使表中元素仍递增有序。
 * 思路：二分查找，找到后执行交换操作，若未找到则标记位置执行插入操作
 */
void SearchExchangeInsert(SqList *A, int x)
{
    int n = A->length;
    int low = 0, high = n - 1, mid; // low 和 high 指向顺序表下界和上界的下标
    while (low <= high)
    {
        mid = (low + high) / 2; // 找中间位置
        if (A->data[mid] == x)
            break; // 找到 x，退出 while 循环
        else if (A->data[mid] < x)
            low = mid + 1; // 到中点mid的右半部去查
        else
            high = mid - 1; // 到中点 mid 的左半部去查
    } // 下面两个 if 语句只会执行一个
    int i, t;
    if (A->data[mid] == x && mid != n - 1)
    { // 若最后一个元素与x相等，则不存在与其后继交换的操作
        t = A->data[mid];
        A->data[mid] = A->data[mid + 1];
        A->data[mid + 1] = t;
    }
    if (low > high)
    { // 查找失败，插入数据元素x
        for (i = n - 1; i > high; i--)
        {
            A->data[i + 1] = A->data[i]; // 后移元素
            A->data[i + 1] = x;
        }
    }
}

/**
 * 王道2.2.3.09.给定三个序列 A、B、C，长度均为n，且均为无重复元素的递增序列，
 * 请设计一个时间上尽可能高效的算法，逐行输出同时存在于这三个序列中的所有元素。
 * 例如，数组A为{1,2,3}，数组B为{2,3,4}，数组C为{-1,0,2}，则输出 2。
 * 要求:
 *      1)给出算法的基本设计思想。
 *      2)根据设计思想，采用C或 C++语言描述算法，关键之处给出注释。
 *      3)说明你的算法的时间复杂度和空间复杂度。
 *
 * 思路：三只指针，定义i,j,k.同时遍历A,B,C.每次将i，j,k对应的最小元素++.
 *      若三个元素相等则输出并且i，j，k，同时++。
 * 时间复杂度：因为i,j,k均只遍历一次各自对应的数组所以执行次数为O（3n），所以时间复杂度为O（n）。
 * 空间复杂度：未使用额外数组，所以为O（1）
 */
void samekey(int A[], int B[], int C[], int n)
{
    int i = 0, j = 0, k = 0; // 定义三个工作指针
    while (i < n && j < n && k < n)
    {
        if (A[i] == B[j] && B[j] == C[k])
        {
            cout << A[i] << endl;
            i++;
            j++;
            k++;
        }
        else
        {
            int maxNum = max(A[i], max(B[j], C[k]));
            if (A[i] < maxNum)
                i++;
            if (B[j] < maxNum)
                j++;
            if (C[k] < maxNum)
                k++;
        }
    }
}

/**
 * 王道2.2.3.10.【2010统考真题]
 * 设将n(n>1)个整数存放到一维数组R中。
 * 设计一个在时间和空间两方面都尽可能高效的算法。将R中保存的序列循环左移p(0<p<n)个位置，
 * 即将R中的数据由(Xo,x1,.,xn-1)变换为(xmx+1,..,xπ-1,X0,X1,..,X0-1).
 * 要求:1)给出算法的基本设计思想。
 *      2)根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。
 *      3) 说明你所设计算法的时间复杂度和空间复杂度。
 * 思路:参考第7题
 * 时间复杂度：各次逆转时间复杂度分别为0(p/2)、0((n-p)/2)和0(n/2),
 *            故所设计的算法的时间复杂度为0(n)，
 * 空间复杂度为0(1)。
 */
void reverse(int R[], int from, int to)
{
    int i, temp;
    for (i = 0; i < (to - from + 1) / 2; i++)
    {
        temp = R[from + i];
        R[from + i] = R[to - i];
        R[to - i] = temp;
    }
}
void converse(int R[], int n, int p)
{
    reverse(R, 0, p - 1);
    reverse(R, p, n - 1);
    reverse(R, 0, n - 1);
}

/**
 * 王道2.2.3.11.【2011 统考真题]一个长度为L(L≥1)的升序序列S，处在第[L/2]个位置的数称为S的中位数。
 * 例如，若序列S=(11,13,15,17,19),则S的中位数是15，两个序列的中位数是含它们所有元素的升序序列的中位数。
 * 例如，若S2=(2,4,6,8,20)，则S和S2的中位数是11。
 * 现在有两个等长升序序列A和B，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列A和B的中位数。
 * 要求:
 *      1) 给出算法的基本设计思想。
 *      2)根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。
 *      3)说明你所设计算法的时间复杂度和空间复杂度。
 * 思路:二分法：1.分别求两个升序序列A、B的中位数，设为a和b，
 *             2.然后求序列4、B的中位数:
 *                  1.若a=b，则a和b为所求中位数，输出，结束算法
 *                  2.若a<b，则舍去A中较小的一半和B中较大的一半，要求两次舍弃长度相等
 *                  3.若a>b，则舍去A中较大的一半和B中较小的一半，要求两次舍弃长度相等
 *             3.重复2
 * 时间复杂度：O（logn）
 * 空间复杂度：O(1)
 */
int findTwoArraysMid(int A[], int B[], int n)
{
    int startA = 0, startB = 0, endA = n - 1, endB = n - 1;
    while (startA != endA && startB != endB)
    {
        int midA = (startA + endA) / 2;
        int midB = (startB + endB) / 2;
        if (A[midA] = B[midB])
            return A[midA];
        if (A[midA] < B[midB])
        {
            if ((startA + endA) % 2 == 0) // 序列长度为奇数
            {
                startA = midA;
                endB = midB;
            } // 否则就是偶数
            startA = midA + 1;
            endB = midB;
        }
        if (A[midA] > B[midB])
        {
            if ((startA + endA) % 2 == 0) // 序列长度为奇数
            {
                endA = midA;
                startB = midB;
            } // 否则就是偶数
            endA = midA;
            startB = midB + 1;
        }
    }

    return A[startA] < B[startB] ? A[startA] : B[startB];
}

/**
 * 王道2.2.3.12.[2013统考真题]已知一个整数序列A=(a0,a1,...,an-1)，其中0≤ai<n(0≤i<n)。
 * 若存在ap1=ap2=...=apm=x且m>n/2(0≤p<n,1≤k≤m),则称x为A的主元素。
 * 例如 A=(0,5,5,3,5,7,5,5),则5为主元素;又如A=(0,5,5,3,5,1,5,7),则A中没有主元素。
 * 假设A中的n个元素保存在一个一维数组中，请设计一个尽可能高效的算法，
 * 找出A的主元素。若存在主元素，则输出该元素;否则输出-1。
 * 要求:
 *      1)给出算法的基本设计思想。
 *      2)根据设计思想，采用C或 C++或Java 语言描述算法，关键之处给出注释。
 *      3)说明你所设计算法的时间复杂度和空间复杂度。
 *
 * 思路：
 *      1.定义一个哨兵元素temp = a[0]，定义一个计数器count = 1。
 *      2.遍历数组，寻找主元素候选
 *          1.若count<0，更新temp为当前元素
 *          2.若temp = 当前元素，则count++；
 *          3.若temp != 当前元素则count--；
 *      3.判断是否为真正主元素。若count > n/2,则temp一定为主元素，
 *      若count > 0再次遍历数组，统计temp出现次数,分析temp是否为主元素，其余情况不存在主元素
 * 时间复杂度：两次循环遍历数组，执行次数为O（2n），所以时间复杂度为O（n）
 * 空间复杂度：O(1)
 */
int Majority(int A[], int n)
{
    int i, temp = A[0], count = 1;
    for (i = 1; i < n; i++)
    {
        if (A[i] == temp)
            count++;
        else if (count > 0)
            count--;
        else
        {
            temp = A[i];
            count = 1;
        }
    }
    if (count > 0)
    {
        for (i = count = 0; i < n; i++)
        {
            if (A[i] == temp)
                count++;
        }
    }
    if (count > n / 2)
        return temp;
    else
        return -1;
}

/**
 * 王道2.2.3.13.【2018统考真题]给定一个含n(n≥1)个整数的数组，
 * 请设计一个在时间上尽可能高效的算法，找出数组中未出现的最小正整数。
 * 例如，数组{-5,3,2,3}中未出现的最小正整数是 1; 数组{1,2,3}中未出现的最小正整数是4。
 * 要求:
 *      1) 给出算法的基本设计思想。
 *      2)根据设计思想，采用C或 C++语言描述算法，关键之处给出注释。
 *      3)说明你所设计算法的时间复杂度和空间复杂度。
 * 思路：要求在时间上尽可能高效，因此采用空间换时间的办法。
 * 分配一个用于标记的数组B[n]，用来记录 A 中是否出现了 1~n 中的正整数，
 * B[0]对应正整数1，B[n-1]对应正整数 n，初始化 B中全部为 0。
 * 由于A中含有n个整数，因此可能返回的值是1~n+1，当中n个数恰好为1~n时返回 n+1。
 * 当数组A中出现了小于或等于0或大于n的值时，会导致1~n中出现空余位置，返回结果必然在1~n中，
 * 因此对于A中出现了小于或等于0或大于n的值，可以不采取任何操作。
 * 算法：1.从A[0]开始遍历A
 *          若 0<A[i]<=n,则令B[A[i] - 1]=1;否则A[i]为负不做操作。
 *      2.对A遍历结束后，开始遍历数组B，
 *          1.若能查找到第一个满足B[i]=0的下标i,返回 i+1即为结果，
 *          2.若B[i]全部不为0，返回 i+1(跳出循环时 i=n，i+1 等于 n+1)，
 *          此时说明A中未出现的最小正整数是 n+1。
 *
 * 时间复杂度:遍历A一次，遍历B一次，两次循环内操作步骤为O(1)量级，因此时间复杂度为 O(n)。
 * 空间复杂度:额外分配了B[n]，空间复杂度为O(n)。
 */
int findMissMin(int A[], int n)
{
    int i, *B;
    B = (int *)malloc(sizeof(int) * n); // 分配空间
    memset(B, 0, sizeof(int) * n);      // 赋初值为 0
    for (i = 0; i < n; i++)
        if (A[i] > 0 && A[i] <= n)
            B[A[i] - 1] = 1;
    for (i = 0; i < n; i++)
        if (B[i] == 0)
            break;
    return i + 1;
}

/**
 * 王道2.2.3.14.【2020统考真题]
 * 定义三元组(a,b,c)(a,b,c均为整数)的距离D=|a-b|+|b-c|+|c-a|,
 * 给定3个非空整数集合S1、S2和S3,按升序分别存储在3个数组中。
 * 请设计一个尽可能高效的算法，计算并输出所有可能的三元组(a,b, c) (a∈S，b∈S2,cES3)中的最小距离。
 * 例如 S1={-1,0,9}，S2={-25,-10,10, 11}，S3={2, 9, 17,30,41}，则最小距离为2,i
 * 相应的三元组为(9, 10, 9)。
 * 要求:
 *      1) 给出算法的基本设计思想。
 *      2)根据设计思想，采用C语言或C++语言描述算法，关键之处给出注释。
 *      3)说明你所设计算法的时间复杂度和空间复杂度。
 * 分析:1.当a=b=c时，距离最小。
 *      2.其余情况。假设 a≤b≤c,L=|a-b|，L=|b-c|，Lз=|c-a|
 *      D=|a-b|+|b-c|+|c-α|≥0=L1+L2+L3=2L3
 * 由D的表达式可知，事实上决定D大小的关键是a和c之间的距离，
 * 于是问题就可以简化为每次固定c找一个 a，使得 L=|c-a|最小。
 *
 * 算法的基本设计思想:
 * ① 使用 Dmin记录所有已处理的三元组的最小距离，初值为一个足够大的整数。
 * ② 集合S1、S2,和S3,分别保存在数组 A、B、C中。数组的下标变量i=j=k=0，
 * 当i<|S1|、j<|S2|且 k<|S3|时(|S]表示集合S中的元素个数)，循环执行下面的 a)~c)。
 *      a)计算(A[],BU],C[])的距离D; (计算 D)
 *      b)若D<D„imn，则 D„=D;(更新 D)
 *      c)将 A[]、B[]、C[]中的最小值的下标+1;
 *      (对照分析:最小值为a，最大值为c，这里c不变而更新 a，试图寻找更小的距离 D)
 * ③ 输出 Dmin，结束。
 * 时间复杂度为:O(n)
 * 空间复杂度为:O(1)
 */
int abs(int a)
{ // 计算绝对值
    if (a < 0)
        return a;
    else
        return a;
}
bool xls_min(int a, int b, int c)
{ // a 是否是三个数中的最小值
    if (a <= b && a <= c)
        return true;
    return false;
}
int findMinofTrip(int A[], int n, int B[], int m, int C[], int p)
{
    // D min 用于记录三元组的最小距离，初值赋为 INT_MAX
    int i = 0, j = 0, k = 0, D_min = INT_MAX, D;
    while (i < n && j < m && k < p && D_min > 0)
    {
        D = abs(A[i] - B[j]) + abs(B[j] - C[k]) + abs(C[k] - A[4]); // 计算D
        if (D < D_min)
            D_min = D; // 更新 D
        if (xls_min(A[i], B[j], C[k]))
            i++; // 更新a
        else if (xls_min(B[j], C[k], A[i]))
            j++;
        else
            k++;
        return D_min;
    }
}

/**
 * leetcode 1.两数之和
 * 给定一个整数数组 nums 和一个整数目标值 target，
 * 请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。
 * 你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。你可以按任意顺序返回答案。
 * 示例 1：
 *      输入：nums = [2,7,11,15], target = 9
 *      输出：[0,1]
 * 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
 * 示例 2：
 *      输入：nums = [3,2,4], target = 6
 *      输出：[1,2]
 * 示例 3：
 *      输入：nums = [3,3], target = 6
 *      输出：[0,1]
 * 提示：
 *      2 <= nums.length <= 10⁴
 *      -10⁹ <= nums[i] <= 10⁹
 *      -10⁹ <= target <= 10⁹
 * 只会存在一个有效答案
 *
 * 思路：当我们使用遍历整个数组的方式寻找 target - x 时，
 * 需要注意到每一个位于 x 之前的元素都已经和 x 匹配过，因此不需要再进行匹配。
 * 而每一个元素不能被使用两次，所以我们只需要在 x 后面的元素中寻找 target - x。
 *
 * 时间复杂度：O（n）
 * 空间复杂度：O（1）
 */
vector<int> twoSum(vector<int> &nums, int target)
{
    unordered_map<int, int> hashtable;
    for (int i = 0; i < nums.size(); ++i)
    {
        auto it = hashtable.find(target - nums[i]);
        if (it != hashtable.end()) // it没有指向unordered_map尾部说明在hashtable中找到了 （target - nums[i]）
        {
            return {it->second, i}; // 查找到合适的元素，返回容器元素和当前元素
        }
        hashtable[nums[i]] = i; //
    }
    return {}; // 没找到，返回空
}

/**
 * leetcode 9.回文数
 * 给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。
 * 回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
 * 例如，121 是回文，而 123 不是。
 * 示例 1：
 *      输入：x = 121
 *      输出：true
 * 示例 2：
 *      输入：x = -121
 *      输出：false
 *      解释：从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
 * 示例 3：
 *      输入：x = 10
 *      输出：false
 *      解释：从右向左读, 为 01 。因此它不是一个回文数。
 * 提示：
 *      -231 <= x <= 231 - 1
 *
 * 思路：
 *      1.负数，最后一位是0肯定不是回文数
 *      2.只有一位肯定是
 *      3.将该数字取后半部分并反转然后逐个和前半部分比较，若有不一致则不是回文数，否则是
 * 时间复杂度：O（n）
 * 空间复杂度：O（1）
 */
bool isPalindrome(int x)
{
    if (x < 0 || (x % 10 == 0 && x != 0))
        return false;
    if (x < 10)
        return true;

    int revertedNumber = 0;
    while (x > revertedNumber)
    {
        revertedNumber = revertedNumber * 10 + x % 10;
        x /= 10;
    }

    // 当数字长度为奇数时，我们可以通过 revertedNumber/10 去除处于中位的数字。
    // 例如，当输入为 12321 时，在 while 循环的末尾我们可以得到 x = 12，revertedNumber = 123，
    // 由于处于中位的数字不影响回文（它总是与自己相等），所以我们可以简单地将其去除。
    return x == revertedNumber || x == revertedNumber / 10;
}

/**
 * leetcode 26.删除有序数组中的重复项
 * 给你一个 非严格递增排列 的数组 nums ，请你原地删除重复出现的元素，
 * 使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。
 * 然后返回 nums 中唯一元素的个数。
 * 考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：
 *      更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。
 *      nums 的其余元素与 nums 的大小不重要。返回 k 。
 * 示例 1：
 *      输入：nums = [1,1,2]
 *      输出：2, nums = [1,2,_]
 * 解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。
 * 不需要考虑数组中超出新长度后面的元素。
 * 示例 2：
 *      输入：nums = [0,0,1,1,1,2,2,3,3,4]
 *      输出：5, nums = [0,1,2,3,4]
 * 解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。
 *      不需要考虑数组中超出新长度后面的元素。
 * 示例 3：
 *      输入：x = 10
 *      输出：false
 *      解释：从右向左读, 为 01 。因此它不是一个回文数。
 * 提示：
 *      1 <= nums.length <=3 * 10⁴
 *      -10⁴ <= nums[i] <= 10⁴
 *      nums 已按 非严格递增 排列
 *
 * 思路：双指针:定义两个数i = 0,j = 1.用i遍历数组，
 *      若i后面一个数与i对应的数不相等则i++，将该数放到j位置上去，最后返回j作为新数组长度
 * 时间复杂度：O（n）
 * 空间复杂度：O（1）
 */
int removeDuplicates(vector<int> &nums)
{
    int j = 1;
    for (int i = 0; i < nums.size() - 1; i++)
    {
        if (nums[i] != nums[i + 1])
        {
            nums[j++] = nums[i + 1];
        }
    }
    return j;
}

/**
 * leetcode 27.移除元素
 * 给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。
 * 元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。
 * 假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：
 *      1.更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。
 * nums 的其余元素和 nums 的大小并不重要。
 *      2.返回 k。
 * 示例 1：
 *      输入：nums = [3,2,2,3], val = 3
 *      输出：2, nums = [2,2,_,_]
 * 解释：你的函数函数应该返回 k = 2, 并且 nums 中的前两个元素均为 2。
 * 你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。
 * 示例 2：
 *      输入：nums = [0,1,2,2,3,0,4,2], val = 2
 *      输出：5, nums = [0,1,4,0,3,_,_,_]
 * 解释：你的函数应该返回 k = 5，并且 nums 中的前五个元素为 0,0,1,3,4。注意这五个元素可以任意顺序返回。
 * 你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。
 * 提示：
 *      0 <= nums.length <= 100
 *      0 <= nums[i] <= 50
 *      0 <= val <= 100
 *
 * 思路：快速排序思想，使用双指针:
 *      1.定义两个数i = 0,j = num.size().i从前往后遍历数组，j从后往前遍历数组
 *      2.若num[i] = value,则将j对应的元素赋值到i的位置，j向左移动一位;
 *      3.若num[i] != value,k++,i向右移动一位
 *
 * 时间复杂度：O（n）
 * 空间复杂度：O（1）
 */
int removeElement(vector<int> &nums, int val)
{
    int i = 0, j = nums.size() - 1;
    while (i < j)
    {
        if (nums[i] == val)
        {
            nums[i] = nums[j--];
        }
        else
        {
            i++;
        }
    }
    return i;
}

/**
 * leetcode 33.搜索旋转排序数组
 * 整数数组 nums 按升序排列，数组中的值 互不相同 。
 * 在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，
 * 使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。
 * 例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
 * 给你 旋转后 的数组 nums 和一个整数 target ，
 * 如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
 * 你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
 * 示例 1：
 *      输入：nums = [4,5,6,7,0,1,2], target = 0
 *      输出：4
 * 示例 2：
 *      输入：nums = [4,5,6,7,0,1,2], target = 3
 *      输出：-1
 * 示例 3：
 *      输入：nums = [1], target = 0
 *      输出：-1
 * 提示：
 *      0 <= nums.length <= 500
 *      -10⁴ <= nums[i] <= 10⁴
 *      -10⁴ <= target <= 10⁴
 *      nums 中的每个值都 独一无二
 *      题目数据保证 nums 在预先未知的某个下标上进行了旋转
 *
 * 思路：二分法
 * 可以发现的是，我们将数组从中间分开成左右两部分的时候，
 * 一定有一部分的数组是有序的。
 * 拿示例来看，我们从 6 这个位置分开以后数组变成了 [4, 5, 6] 和 [7, 0, 1, 2] 两个部分，
 * 其中左边 [4, 5, 6] 这个部分的数组是有序的，其他也是如此。
 * 在常规二分查找的时候查看当前 mid 为分割位置分割出来的两个部分 [l, mid] 和 [mid + 1, r] 哪个部分是有序的，
 * 若该段数据中，段首<段尾则该段是有序的
 * 并根据有序的那个部分确定我们该如何改变二分查找的上下界，因为我们能够根据有序的那部分判断出 target 在不在这个部分：
 * 如果 [l, mid - 1] 是有序数组，且 target 的大小满足 [nums[l],nums[mid])，
 * 则我们应该将搜索范围缩小至 [l, mid - 1]，否则在 [mid + 1, r] 中寻找。
 * 如果 [mid, r] 是有序数组，且 target 的大小满足 (nums[mid+1],nums[r]]，
 * 则我们应该将搜索范围缩小至 [mid + 1, r]，否则在 [l, mid - 1] 中寻找。
 *
 * 时间复杂度：O（logn）
 * 空间复杂度：O（1）

作者：力扣官方题解
链接：https://leetcode.cn/problems/search-in-rotated-sorted-array/solutions/220083/sou-suo-xuan-zhuan-pai-xu-shu-zu-by-leetcode-solut/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 */
int search(vector<int> &nums, int target)
{
    int n = (int)nums.size();
    if (!n)
    {
        return -1;
    }
    if (n == 1)
    {
        return nums[0] == target ? 0 : -1;
    }
    int l = 0, r = n - 1;
    while (l <= r)
    {
        int mid = (l + r) / 2;
        if (nums[mid] == target)
            return mid;
        if (nums[0] <= nums[mid])
        {
            if (nums[0] <= target && target < nums[mid])
            {
                r = mid - 1;
            }
            else
            {
                l = mid + 1;
            }
        }
        else
        {
            if (nums[mid] < target && target <= nums[n - 1])
            {
                l = mid + 1;
            }
            else
            {
                r = mid - 1;
            }
        }
    }
    return -1;
}

// class Solution
// {
// public:
//     int search(vector<int> &nums, int target)
//     {
//         int lo = 0, hi = nums.size() - 1;
//         while (lo < hi)
//         {
//             int mid = (lo + hi) / 2;
//             if ((nums[0] > target) ^ (nums[0] > nums[mid]) ^ (target > nums[mid]))
//                 lo = mid + 1;
//             else
//                 hi = mid;
//         }
//         return lo == hi && nums[lo] == target ? lo : -1;
//     }
// };

/**
 * leetcode 35.搜索插入位置
 * 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。
 * 如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
 *
 * 请必须使用时间复杂度为 O(log n) 的算法。
 *
 * 示例 1:
 *      输入: nums = [1,3,5,6], target = 5
 *      输出: 2
 * 示例 2:
 *      输入: nums = [1,3,5,6], target = 2
 *      输出: 1
 * 示例 3:
 *      输入: nums = [1,3,5,6], target = 7
 *      输出: 4
 *
 *      1 <= nums.length <= 10⁴
 *      -10⁴ <= nums[i] <= 10⁴
 *      -10⁴ <= target <= 10⁴
 *      nums 为 无重复元素 的 升序 排列数组
 *
 * 思路：二分查找
 * 时间复杂度：O（logn）
 * 空间复杂度：O（1）
 */
int searchInsert(vector<int> &nums, int target)
{
    int n = nums.size();
    int left = 0, right = n - 1, ans = n;
    while (left <= right)
    {
        int mid = ((right - left) >> 1) + left;
        if (target <= nums[mid])
        {
            ans = mid;
            right = mid - 1;
        }
        else
        {
            left = mid + 1;
        }
    }
    return ans;
}

/**
 * leetcode 41.缺失的第一个正数
 * 给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
 * 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
 * 示例 1：
 *      输入：nums = [1,2,0]
 *      输出：3
 *      解释：范围 [1,2] 中的数字都在数组中。
 * 示例 2：
 *      输入：nums = [3,4,-1,1]
 *      输出：2
 *      解释：1 在数组中，但 2 没有。
 * 示例 3：
 *      输入：nums = [7,8,9,11,12]
 *      输出：1
 *      解释：最小的正数 1 没有出现。
 * 提示：
 *      1 <= nums.length <= 10⁵
 *      -2³¹ <= nums[i] <= 2³¹ - 1
 *
 * 思路1：先排序，再遍历
 *  时间复杂度O（nlogn)
 *  空间复杂度：O（n）
 *
 * 思路2：
 *      1.将数组中所有小于等于 0 的数修改为 N+1；
 *      2.我们遍历数组中的每一个数 x，它可能已经被打了标记，因此原本对应的数为 ∣x∣。
 *  如果 ∣x∣∈[1,N]，那么我们给数组中的第 ∣x∣−1 个位置的数添加一个负号。注意如果它已经有负号，不需要重复添加；
 *      3.在遍历完成之后，如果数组中的每一个数都是负数，那么答案是 N+1，否则答案是第一个正数的位置加 1。
 * 时间复杂度：O（n）
 * 空间复杂度：O（1）
 *
 * 思路3：遍历数组将数组元素放在下标位置上，nums[i]<0||nums[i]>n不用管
 * 时间复杂度：O（n）
 * 空间复杂度：O（1）
 */
int firstMissingPositive(vector<int> &nums)
{
    int n = nums.size();
    for (int i = 0; i < n; ++i)
    {
        while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i])
        {
            swap(nums[nums[i] - 1], nums[i]);
        }
    }
    for (int i = 0; i < n; ++i)
    {
        if (nums[i] != i + 1)
        {
            return i + 1;
        }
    }
    return n + 1;
}

/**
 * leetcode 58.最后一个单词的长度
 * 给你一个字符串 s，由若干单词组成，单词前后用一些空格字符隔开。
 * 返回字符串中 最后一个 单词的长度。
 * 单词 是指仅由字母组成、不包含任何空格字符的最大子字符串。
 * 示例 1：
 *      输入：s = "Hello World"
 *      输出：5
 *      解释：最后一个单词是“World”，长度为 5。
 * 示例 2：
 *      输入：s = "   fly me   to   the moon  "
 *      输出：4
 * 示例 3：
 *      输入：s = "luffy is still joyboy"
 *      输出：6
 * 思路：首先找到字符串中的最后一个字母，该字母即为最后一个单词的最后一个字母。
 * 从最后一个字母开始继续反向遍历字符串，直到遇到空格或者到达字符串的起始位置。
 * 遍历到的每个字母都是最后一个单词中的字母，因此遍历到的字母数量即为最后一个单词的长度。
 * 时间复杂度：O（n）
 * 空间复杂度：O（1）
 */
int lengthOfLastWord(string s)
{
    int index = s.size() - 1;

    while (s[index] == ' ')
    {
        index--;
    }
    int wordLength = 0;
    while (index >= 0 && s[index] != ' ')
    {
        wordLength++;
        index--;
    }

    return wordLength;
}

/**
 * leetcode 66.加一
 * 思路：模拟数学加法运算
 * 时间复杂度：O（n）
 * 空间复杂度：O（1）
 */
vector<int> plusOne(vector<int> &digits)
{
    int n = digits.size();
    for (int i = n - 1; i >= 0; --i)
    {
        if (digits[i] != 9)
        {
            ++digits[i];
            for (int j = i + 1; j < n; ++j)
            {
                digits[j] = 0;
            }
            return digits;
        }
    }

    // digits 中所有的元素均为 9
    vector<int> ans(n + 1);
    ans[0] = 1;
    return ans;
}

/**
 * leetcode 169.多数元素
 * 给定一个大小为 n 的数组 nums ，返回其中的多数元素。
 * 多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
 * 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
 * 示例 1：
 *      输入：nums = [3,2,3]
 *      输出：3
 * 示例 2：
 *      输入：nums = [2,2,1,1,1,2,2]
 *      输出：2
 * 提示：
 *      n == nums.length
 *      1 <= n <= 5 * 10⁴
 *      -10⁹ <= nums[i] <= 10⁹
 *
 * 思路：如果我们把众数记为 +1，把其他数记为 −1，将它们全部加起来，显然和大于 0，从结果本身我们可以看出众数比其他数多。
 *      1.遍历数组，寻找主元素候选
 *          1.若count<0，更新temp为当前元素
 *          2.若temp = 当前元素，则count++；
 *          3.若temp != 当前元素则count--；
 *      3.判断是否为真正主元素。若count > 0,则temp一定为众数。
 * 时间复杂度：O（n）
 * 空间复杂度：O（1）
 */
int majorityElement(vector<int> &nums)
{
    int candidate = -1;
    int count = 0;
    for (int num : nums)
    {
        if (num == candidate)
            ++count;
        else if (--count < 0)
        {
            candidate = num;
            count = 1;
        }
    }
    return candidate;
}

/**
 * *********************************************************************************************************************
 * *******************************************************串********************************************************
 * *********************************************************************************************************************
 */

/**
 * leetcode 28.找出字符串中第一个匹配项的下标
 * 给你两个字符串 haystack 和 needle ，
 * 请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。
 * 如果 needle 不是 haystack 的一部分，则返回  -1 。
 * 示例 1：
 *      输入：haystack = "sadbutsad", needle = "sad"
 *      输出：0
 * 解释："sad" 在下标 0 和 6 处匹配。第一个匹配项的下标是 0 ，所以返回 0 。
 * 示例 2：
 *      输入：haystack = "leetcode", needle = "leeto"
 *      输出：-1
 * 解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。
 * 提示：
 *      1 <= haystack.length, needle.length <= 10⁴
 *      haystack 和 needle 仅由小写英文字符组成
 *
 * 思路：使用双指针:
 *      1.定义两个数i = 0,j = 0.从前往后遍历串
 *      2.若haystack[i] = needle[0],则将i赋值给j,然后i逐个向后移，同时将needle中的元素和i比较，
 *      3.若needle与i匹配则返回j的值，否则重复2，致完成遍历
 * 时间复杂度：O（mn）
 * 空间复杂度：O（1）
 */
int strStr(string haystack, string needle)
{
    int m = needle.size(), n = haystack.size();
    for (int i = 0; i + m <= n; i++)
    {
        bool tag = true;
        for (int j = 0; j < m; j++)
        {
            if (haystack[i + j] != needle[j])
            {
                tag = false;
                break;
            }
        }
        if (tag)
        {
            return i;
        }
    }

    return -1;
}

/**
 * leetcode 125.验证回文串
 * 如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。
 * 则可以认为该短语是一个 回文串 。
 * 字母和数字都属于字母数字字符。
 * 给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。
 *
 * 思路：
 * 直接在原字符串 s 上使用双指针。
 * 在移动任意一个指针时，需要不断地向另一指针的方向移动，
 * 直到遇到一个字母或数字字符，或者两指针重合为止。
 * 也就是说，我们每次将指针移到下一个字母字符或数字字符，再判断这两个指针指向的字符是否相同。
 * 时间复杂度：O（n）
 * 空间复杂度：O（1）
 */
bool isPalindrome(string s)
{
    int n = s.size();
    int left = 0, right = n - 1;
    while (left < right)
    {
        while (left < right && !isalnum(s[left]))
        {
            ++left;
        }
        while (left < right && !isalnum(s[right]))
        {
            --right;
        }
        if (left < right)
        {
            if (tolower(s[left]) != tolower(s[right]))
            {
                return false;
            }
            ++left;
            --right;
        }
    }
    return true;
}

/**
 * leetcode 389.找不同
 * 给定两个字符串 s 和 t ，它们只包含小写字母。
 * 字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。
 * 请找出在 t 中被添加的字母。
 * 示例 1：
 *      输入：s = "abcd", t = "abcde"
 *      输出："e"
 *      解释：'e' 是那个被添加的字母。
 * 示例 2：
 *      输入：s = "", t = "y"
 *      输出："y"
 * 提示：
 *      0 <= s.length <= 1000
 *      t.length == s.length + 1
 *      s 和 t 只包含小写字母
 * 思路：将将字符串 s 中每个字符的 ASCII 码的值求和，得到 sumA；
 * 对字符串 t 同样的方法得到 sumt。两者的差值 sumA−sumt 即代表了被添加的字符。
 * 时间复杂度：O（n）
 * 空间复杂度：O（1）
 */
char findTheDifference(string s, string t)
{
    int as = 0, at = 0;
    for (char ch : s)
    {
        as += ch;
    }
    for (char ch : t)
    {
        at += ch;
    }
    return at - as;
}

/**
 * leetcode 434.字符串中的单词数
 * 统计字符串中的单词个数，这里的单词指的是连续的不是空格的字符。
 * 请注意，你可以假定字符串里不包括任何不可打印的字符。
 *
 * 示例:
 *      输入: "Hello, my name is John"
 *      输出: 5
 *      解释: 这里的单词是指连续的不是空格的字符，所以 "Hello," 算作 1 个单词。
 * 思路：计算字符串中单词的数量，就等同于计数单词的第一个下标的个数。
 * 因此，我们只需要遍历整个字符串，统计每个单词的第一个下标的数目即可。
 * 满足单词的第一个下标有以下两个条件：
 *      1.该下标对应的字符不为空格；
 *      2.该下标为初始下标或者该下标的前下标对应的字符为空格；
 * 时间复杂度：O（n）
 * 空间复杂度：O（1）
 */
int countSegments(string s)
{
    int segmentCount = 0;
    for (int i = 0; i < s.size(); i++)
    {
        if ((i == 0 || s[i - 1] == ' ') && s[i] != ' ')
        {
            segmentCount++;
        }
    }
    return segmentCount;
}

/**
 * leetcode 448.找到数组中所有消失的数字
 * 给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。
 * 请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。
 * 示例 1：
 *      输入：nums = [4,3,2,7,8,2,3,1]
 *      输出：[5,6]
 * 示例 2：
 *      输入：nums = [1,1]
 *      输出：[2]
 * 时间复杂度：O（n）
 * 空间复杂度：O（1）
 */
vector<int> findDisappearedNumbers(vector<int> &nums)
{
    int n = nums.size();
    for (auto &num : nums)
    {
        int x = (num - 1) % n;
        nums[x] += n;
    }
    vector<int> ret;
    for (int i = 0; i < n; i++)
    {
        if (nums[i] <= n)
        {
            ret.push_back(i + 1);
        }
    }
    return ret;
}

/**
 * leetcode 844.含退格的字符串
 * 给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。
 * # 代表退格字符。注意：如果对空文本输入退格字符，文本继续为空。
 * 示例 1：
 *      输入：s = "ab#c", t = "ad#c"
 *      输出：true
 *      解释：s 和 t 都会变成 "ac"。
 * 示例 2：
 *      输入：s = "ab##", t = "c#d#"
 *      输出：true
 *      解释：s 和 t 都会变成 ""。
 * 示例 3：
 *      输入：s = "a#c", t = "b"
 *      输出：false
 *      解释：s 会变成 "c"，但 t 仍然是 "b"。
 * 思路：将给定的字符串中的退格符和应当被删除的字符都去除，还原给定字符串的一般形式。
 * 然后直接比较两字符串是否相等即可。
 * 创建一个栈，遍历字符串如果它是退格符，那么我们将栈顶弹出；
 * 如果它是普通字符，那么我们将其压入栈中。
 * 时间复杂度：O（n）
 * 空间复杂度：O（1）
 */
bool backspaceCompare(string S, string T)
{
    return build(S) == build(T);
}

string build(string str)
{
    string ret;
    for (char ch : str)
    {
        if (ch != '#')
        {
            ret.push_back(ch);
        }
        else if (!ret.empty())
        {
            ret.pop_back();
        }
    }
    return ret;
}

/**
 * 输入两个串，判断B是否为A的子串
 * 输入： abcde bcd 输出： YES
 * 输入： ababa abc 输出NO
 * 双指针：我们初始化两个指针 i 和 j，分别指向 s 和 t 的初始位置。每次贪心地匹配，
 * 匹配成功则 i 和 j 同时右移，匹配 s 的下一个位置，匹配失败则 j 右移，i 不变，
 * 尝试用 t 的下一个字符匹配 s。最终如果 i 移动到 s 的末尾，就说明 s 是 t 的子序列。
 * 时间复杂度：O（n + m）
 * 空间复杂度：O（1）
 */
bool isSubsequence(string s, string t)
{
    int n = s.length(), m = t.length();
    int i = 0, j = 0;
    while (i < n && j < m)
    {
        if (s[i] == t[j])
        {
            i++;
        }
        j++;
    }
    return i == n;
}

/**
 * QAQ:输入一行由大写字母组成的字符串，数一数有多少个QAQ？QAQ三个字母任意一个位置不同，则总数+1，
 * 例如QAQQ 位置123，算一个QAQ，而位置124也算一个QAQ，因此共有两个QAQ，答案为2
 * 输入：QAQAQBCDEF输出：4 解释：123，125，145，345 (数字代表字母的位置)，以上共有4个QAQ
 */
int countQAQ(char arr[], int len)
{
    int cnt = 0;
    int pre[MAXSIZE] = {0}; // pre[i]表示从第0个到第i-1个字母有多少Q
    for (int i = 1; i <= len; i++)
    {
        if (arr[i - 1] == 'Q')
            pre[i] = pre[i - 1] + 1;
        else
            pre[i] = pre[i - 1];
    }
    for (int i = 0; i < len; i++)
    {
        if (arr[i] == 'A')
            cnt += pre[i] * (pre[len] - pre[i]);
    }
    return cnt;
}

int main()
{
    // int nums[] = {-3, -2, -1, 0, 1, 2};
    // int length = getLength(nums);
    // rankArrayByAbsoluteValue(nums, length);
    // printArray(nums, length);

    // string a = "QAQAQBCDEF";
    // char temp[] = {'Q','A','Q','A','Q','B','C','D','E','F'};
    // char temp[] = {'Q','A','Q','Q'};
    // int ans = countQAQ(temp,10);
    // cout<<ans<<endl;

    /**判断子串*/
    int a = isSubsequence("abababc", "abd");
    cout << a << endl;

    // system("pause");
    return 0;
}